from typing import Optional

from com.siyuan.ListNode import ListNode


class Solution:

    '''
    双指针
    '''
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # 链表1
        dummy1 = ListNode(0)
        # 连表2
        dummy2 = ListNode(0)
        # 指针1
        p1 = dummy1
        # 指针2
        p2 = dummy2

        while head:
            if head.val < x:
                p1.next = head
                p1 = p1.next
            else:
                p2.next = head
                p2 = p2.next

            # 清除下个节点
            tmp = head.next
            head.next = None
            head = tmp

        # 拼接
        p1.next = dummy2.next
        return dummy1.next
